package com.zs.letcode.search;

import java.util.*;

/**
 * 根据字符出现频率排序
 * 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
 * <p>
 * 示例 1:
 * <p>
 * 输入:
 * "tree"
 * <p>
 * 输出:
 * "eert"
 * <p>
 * 解释:
 * 'e'出现两次，'r'和't'都只出现一次。
 * 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
 * 示例 2:
 * <p>
 * 输入:
 * "cccaaa"
 * <p>
 * 输出:
 * "cccaaa"
 * <p>
 * 解释:
 * 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
 * 注意"cacaca"是不正确的，因为相同的字母必须放在一起。
 * 示例 3:
 * <p>
 * 输入:
 * "Aabb"
 * <p>
 * 输出:
 * "bbAa"
 * <p>
 * 解释:
 * 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
 * 注意'A'和'a'被认为是两种不同的字符。
 * 相关标签
 * 堆
 * 哈希表
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/all-about-lockup-table/fc4ic/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/6/22 10:38
 */
public class Chapter7 {
    public static void main(String[] args) {

    }

    private static class Solution {
        /**
         * 思路一：直接排序
         */
        public String frequencySort(String s) {
            Map<Character, Integer> count = new HashMap<>();
            for (char c : s.toCharArray()) {
                count.put(c, count.getOrDefault(c, 0) + 1);
            }
            List<Map.Entry<Character, Integer>> items = new ArrayList<>(count.entrySet());
            items.sort((o1, o2) -> o2.getValue() - o1.getValue());
            StringBuilder res = new StringBuilder();
            for (Map.Entry<Character, Integer> item : items) {
                char key = item.getKey();
                int val = item.getValue();
                for (int i = 0; i < val; i++) {
                    res.append(key);
                }
            }
            return res.toString();
        }

        /**
         * 思路二：最大堆
         */
        public String frequencySort1(String s) {
            Map<Character, Integer> count = new HashMap<>();
            for (char c : s.toCharArray()) {
                count.put(c, count.getOrDefault(c, 0) + 1);
            }
            PriorityQueue<Map.Entry<Character, Integer>> items = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
            items.addAll(count.entrySet());
            StringBuilder res = new StringBuilder();
            while (!items.isEmpty()) {
                Map.Entry<Character, Integer> item = items.poll();
                char key = item.getKey();
                int val = item.getValue();
                for (int i = 0; i < val; i++) {
                    res.append(key);
                }
            }
            return res.toString();
        }
    }
}
